package Intermediate_algorithm.ArrayAndString;

import org.junit.Test;

/*
最长回文子串
给你一个字符串 s，找到 s 中最长的 回文 子串。
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd"
输出："bb"
作者：LeetCode
链接：https://leetcode.cn/leetbook/read/array-and-string/conm7/
 */
public class _05最长回文子串 {

    @Test
    public void test() {
        System.out.println(longestPalindrome("babad"));
    }

    //DP
    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0) return "";
        int len = s.length();
        boolean[][] dp = new boolean[len][len];
        int res = 1;
        //所有字母必定是回文串
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }
        int begin = 0;
        for (int L = 2; L <= len; L++){
            int left = 0;
            for (left = 0; left < len; left++) {
                int right = L + left - 1;
                if (right >= len){
                    break;
                }
                if (s.charAt(left) == s.charAt(right)){
                    if (L <= 3){
                        dp[left][right] = true;
                    }else {
                        dp[left][right] = dp[left + 1][right - 1];
                    }
                }

                if (dp[left][right] && L > res){
                    res = L;
                    begin = left;
                }
            }
        }
        return s.substring(begin, begin + res);
    }

    //官解：方法二：中心扩展算法
    /*
    作者：力扣官方题解
    链接：https://leetcode.cn/problems/longest-palindromic-substring/solutions/255195/zui-chang-hui-wen-zi-chuan-by-leetcode-solution/
     */
    class Solution {
        public String longestPalindrome(String s) {
            if (s == null || s.length() < 1) {
                return "";
            }
            int start = 0, end = 0;
            for (int i = 0; i < s.length(); i++) {
                int len1 = expandAroundCenter(s, i, i);
                int len2 = expandAroundCenter(s, i, i + 1);
                int len = Math.max(len1, len2);
                if (len > end - start) {
                    start = i - (len - 1) / 2;
                    end = i + len / 2;
                }
            }
            return s.substring(start, end + 1);
        }

        public int expandAroundCenter(String s, int left, int right) {
            while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
                --left;
                ++right;
            }
            return right - left - 1;
        }
    }

}
